package com.jyl.dp;

/**
 * 2. 递归加缓存 --> 处理重复计算问题
 * 时间复杂度：O(n)
 * @ClassName CacheArray
 * @Author admin
 * @Date 2024/6/15
 */
public class CacheArray {

    public static void main(String[] args) {
        for (int i = 0; i <= 100; i++) {
            System.out.println(i + "==" + fib(i));
        }
    }

    private static long[] cache;

    private static long fib(int num) {
        if (cache == null) {
            cache = new long[101];
        }

        if (num == 0) {
            return 0;
        }
        if (num == 1) {
            return 1;
        }

        // 尝试命中缓存
        if (cache[num] > 0) {
            return cache[num];
        }

        long result = fib(num - 1) + fib(num - 2);
        cache[num] = result; // 将每次计算出的值存入缓存数组中

        return result;
    }

}
